/*
 * @lc app=leetcode.cn id=102 lang=cpp
 *
 * [102] 二叉树的层次遍历
 */

// @lc code=start
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct TreeNode
{
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
 public:
  // 递归法 O(n), O(1)
  // 实际上就是用的前序遍历的思想（前序遍历对每一层而言，靠左的先访问，满足层序遍历规律），区别在于每次递归传入了level信息
  /*
  vector<vector<int>> levelOrder(TreeNode* root)
  {
    vector<vector<int>> result;  // 建立可以存放vector的空容器
  }

  void traverse(TreeNode* root, int level, vector<vector<int>>& result)
  {
    if (NULL == root) return;   // 递归的出口（包括递归子函数的出口）
    if (level > result.size())  // 每一层的元素用一个vector装
    {
      result.push_back(
          vector<
              int>());  //
  在下一层时，增加空容器（因为事先不知道树的层数，故要一边遍历，一边增加容器大小）
    }

    result[level - 1].push_back(root->val);  // 将元素值push进第level层的容器（索引从0开始）
    traverse(root->left, level + 1, result);
    traverse(root->right, level + 1, result);  // 最后一个语句return之后，整个递归函数才结束
  }
  */

  // 二叉树的层数遍历不分行打印
  // 来源acwing:符合宽搜的特征而不是DFS
  vector<int> printFromTopToBottom(TreeNode* root)
  {
    vector<int> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    while (q.size())
    {
      auto t = q.front();
      q.pop();
      res.push_back(t->val);
      if (t->left) q.push(t->left);
      if (t->right) q.push(t->right);
    }

    return res;
  }

  // 二叉树的层数遍历分行打印
  // 来源acwing:符合宽搜的特征而不是DFS,在上面的基础上修改
  vector<vector<int>> printFromTopToBottom(TreeNode* root)
  {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    q.push(NULL);  // root层的标识符

    vector<int> cur;
    while (q.size())
    {
      TreeNode* t = q.front();
      q.pop();

      if (t)  // 跟上一道题同样的操作
      {
        cur.push_back(t->val);
        if (t->left) q.push(t->left);
        if (t->right) q.push(t->right);
      }
      else  // 当t首次为NULL时，即根节点/第一层访问完毕，此时第一层需要放入res，对于q来说第一层的孩子(第二层)已经全部放入q,所以此时要放入NULL在下两行
      {
        if (q.size()) q.push(NULL);
        res.push_back(cur);
        cur.clear();
      }
    }
    return res;
  }

  /*
  迭代法，O(n),O(1) 掌握
  层序遍历二叉树是典型的广度优先搜索BFS的应用，但是这里稍微复杂一点的是，我们要把各个层的数分开，存到一个二维向量里面
  用队列实现
  （1）首先根结点入队
  （2）访问队首元素，队首元素出队，若子结点不为空，子结点（下一层的所有结点）入队
  （3）一层一层的访问，直至队列清空
  */

  vector<vector<int>> levelOrder(TreeNode* root)
  {
    vector<vector<int>> res;
    if (nullptr == root) return res;

    queue<TreeNode*> q;
    q.push(root);  // 根结点入队

    while (!q.empty())
    {
      vector<int> level;
      int size = q.size();  // 当前层的结点数，会随着每层结点的push,长度会变化

      for (int i = 0; i < size; i++)  // 遍历该层结点，并将下一层结点入队
      {
        TreeNode* node = q.front();
        level.push_back(node->val);  // 访问当前结点
        q.pop();                     // 出队

        // 将当前结点的左右子结点入队
        if (node->left) q.push(node->left);
        if (node->right) q.push(node.right);
        // 下一层的结点排在上一层结点之后
      }

      res.push_back(level);
    }
    return res;
  }
};
// @lc code=end
